翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

split graph : ウィキペディア英語版
split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by .〔 had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). use the definition given here, which has been followed in the subsequent literature; for instance, it is , Definition 3.2.3, p.41.〕
A split graph may have more than one partition into a clique and an independent set; for instance, the path ''a''–''b''–''c'' is a split graph, the vertices of which can be partitioned in three different ways:
#the clique and the independent set
#the clique and the independent set
#the clique and the independent set
Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).〔; , Theorem 6.3, p. 151.〕
==Relation to other graph families==
From the definition, split graphs are clearly closed under complementation.〔, Theorem 6.1, p. 150.〕 Another characterization of split graphs involves complementation: they are chordal graphs the complements of which are also chordal.〔; , Theorem 6.3, p. 151; , Theorem 3.2.3, p. 41.〕 Just as chordal graphs are the intersection graphs of subtrees of trees, split graphs are the intersection graphs of distinct substars of star graphs.〔; ; , Theorem 4.4.2, p. 52.〕 Almost all chordal graphs are split graphs; that is, in the limit as ''n'' goes to infinity, the fraction of ''n''-vertex chordal graphs that are split approaches one.〔.〕
Because chordal graphs are perfect, so are the split graphs. The double split graphs, a family of graphs derived from split graphs by doubling every vertex (so the clique comes to induce an antimatching and the independent set comes to induce a matching), figure prominently as one of five basic classes of perfect graphs from which all others can be formed in the proof by of the Strong Perfect Graph Theorem.
If a graph is both a split graph and an interval graph, then its complement is both a split graph and a comparability graph, and vice versa. The split comparability graphs, and therefore also the split interval graphs, can be characterized in terms of a set of three forbidden induced subgraphs.〔; , Theorem 9.7, page 212.〕 The split cographs are exactly the threshold graphs, and the split permutation graphs are exactly the interval graphs that have interval graph complements.〔, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.〕 Split graphs have cochromatic number 2.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「split graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.